package com.shangxia.leetcode.hoot100.easy;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.List;

/**
 * @ProjectName: leetcode
 * @ClassName: Solution2
 * @Time: 2020/11/22
 * @Author: zhouy
 * @Description: 回文链表
 * @Experience:
 */

@Slf4j
public class Solution2 {

    public static void main(String[] args) {
        System.out.println(isPalindrome3(new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(2, new ListNode(1)))))));
        System.out.println(isPalindrome3(new ListNode(1, new ListNode(2))));
    }

    /**
     * 234. 回文链表
     *
     * @param head
     * @return
     * @Description:请判断一个链表是否为回文链表。
     */

    /**
     * 快慢指针 + 反转比较
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome4(ListNode head) {
        ListNode fast = head, slow = head;
        //通过快慢指针找到中点 快指针步长2，慢指针步长1
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //如果fast不为空，说明链表的长度是奇数个
        if (fast != null) {
            slow = slow.next;
        }
        //反转后半部分链表
        slow = reverse(slow);

        fast = head;
        while (slow != null) {
            //然后比较，判断节点值是否相等
            if (fast.val != slow.val) {
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }

    //反转链表
    public static ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

    /**
     * 先转数组，在用双指针法
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome2(ListNode head) {
        List<Integer> vals = new ArrayList<>();

        // 将链表的值复制到数组中
        ListNode currentNode = head;
        while (currentNode != null) {
            vals.add(currentNode.val);
            currentNode = currentNode.next;
        }

        // 使用双指针判断是否回文
        int front = 0;
        int back = vals.size() - 1;
        while (front < back) {
            if (!vals.get(front).equals(vals.get(back))) {
                return false;
            }
            front++;
            back--;
        }
        return true;
    }

    /**
     * 哈希公式：hash = hash * seed + val,其中 seed 是一个质数 ，val 是节点的值
     * 准确度不是100%，但快
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome3(ListNode head) {
        long hash1 = 0, hash2 = 0, h = 1;
        long seed = (long) (1e9 + 7);
        ListNode p = head;
        while (p != null) {
            hash1 = hash1 * seed + p.val;
            hash2 = hash2 + h * p.val;
            h *= seed;
            p = p.next;
        }
        return hash1 == hash2;
    }

    /**
     * 蠢办法
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome(ListNode head) {
        if (null == head || null == head.next) {
            return true;
        }
        ListNode node = new ListNode(head.val);
        while (!(equalNode(node, head) || equalNode(node, head.next))) {
            if (head.next == null) {
                return false;
            }
            ListNode node1 = new ListNode(head.next.val);
            node1.next = node;
            node = node1;
            head = head.next;
        }
        return true;
    }


    private static Boolean equalNode(ListNode head1, ListNode head2) {
        if (null == head1 && null == head2) {
            return true;
        }
        if (null == head1 || null == head2) {
            return false;
        }
        if (head1.val != head2.val) {
            return false;
        }
        if (null == head1.next && null == head2.next) {
            return true;
        }
        if (null == head1.next || null == head2.next) {
            return false;
        }
        return equalNode(head1.next, head2.next);
    }


    @Data
    @AllArgsConstructor
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }

    }


}

